package cn.javadog.algorithm.m200_300;


/**
 * @author: yuy
 * @create: 2020-10-29 13:49
 * 209. 长度最小的子数组
 * https://leetcode-cn.com/problems/minimum-size-subarray-sum/
 *
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 输入：s = 7, nums = [2,3,1,2,4,3]
 * 输出：2
 * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 **/
public class Algorithm209 {

    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
        System.out.println(minSubArrayLen(13, new int[]{1,2,3,4,5}));
        System.out.println(minSubArrayLen(15, new int[]{1,2,3,4,5}));
        System.out.println(minSubArrayLen(4, new int[]{1,4,4}));
    }

    /**
     * 滑块，先往后滑倒ok，再左端收缩
     */
    public static int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;

        int leftIdx = 0, rightIdx = 1, minLen = Integer.MAX_VALUE, winSum = nums[0];
        boolean slideRight;
        while (true) {
            // 计算是扩张还是收缩，右滑块必须比左滑块大
            slideRight = winSum < s || rightIdx == leftIdx;
            // 根据结果，调整坐标
            if (slideRight) {
                // slideRight 右滑块向前，窗口增大
                rightIdx++;
                if (rightIdx > nums.length) {
                    break;
                }
                winSum += nums[rightIdx-1];
            }else {
                // 左滑块向前，窗口缩小
                minLen = Math.min(minLen, rightIdx - leftIdx);
                winSum -= nums[leftIdx];
                leftIdx++;
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

}
